//===--- RefCountState.h - Represents a Reference Count ---------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#ifndef POLARPHP_PIL_OPTIMIZER_INTERNAL_ARC_REFCOUNTSTATE_H
#define POLARPHP_PIL_OPTIMIZER_INTERNAL_ARC_REFCOUNTSTATE_H

#include "polarphp/pil/optimizer/internal/arc/RCStateTransition.h"
#include "polarphp/basic/ImmutablePointerSet.h"
#include "polarphp/pil/lang/PILInstruction.h"
#include "polarphp/pil/lang/PILArgument.h"
#include "polarphp/pil/lang/PILBasicBlock.h"
#include "polarphp/pil/lang/InstructionUtils.h"
#include "polarphp/pil/optimizer/analysis/ARCAnalysis.h"
#include "polarphp/pil/optimizer/analysis/EpilogueARCAnalysis.h"
#include "polarphp/pil/optimizer/analysis/RCIdentityAnalysis.h"
#include <algorithm>

namespace polar {
class AliasAnalysis;
} // end namespace polar

//===----------------------------------------------------------------------===//
//                              Ref Count State
//===----------------------------------------------------------------------===//

namespace polar {

/// A struct that abstracts over reference counts manipulated by strong_retain,
/// retain_value, strong_release,
class RefCountState {
protected:
   /// Return the PILValue that represents the RCRoot that we are
   /// tracking.
   PILValue RCRoot;

   /// The last state transition that this RefCountState went through. None if we
   /// have not see any transition on this ref count yet.
   RCStateTransition Transition;

   /// Was the pointer we are tracking known incremented when we visited the
   /// current increment we are tracking? In that case we know that it is safe
   /// to move the inner retain over instructions that may decrement ref counts
   /// since the outer retain will keep the reference counted value alive.
   bool KnownSafe = false;

public:
   RefCountState() = default;
   ~RefCountState() = default;
   RefCountState(const RefCountState &) = default;
   RefCountState &operator=(const RefCountState &) = default;
   RefCountState(RefCountState &&) = default;
   RefCountState &operator=(RefCountState &&) = default;

   /// Initializes/reinitialized the state for I. If we reinitialize we return
   /// true.
   bool initWithMutatorInst(ImmutablePointerSet<PILInstruction> *I,
                            RCIdentityFunctionInfo *RCFI) {
      assert(I->size() == 1);

      // Are we already tracking a ref count modification?
      bool Nested = isTrackingRefCount();

      Transition = RCStateTransition(I);
      assert(Transition.isMutator() && "Expected I to be a mutator!\n");

      // Initialize KnownSafe to a conservative false value.
      KnownSafe = false;

      // Initialize value.
      RCRoot = RCFI->getRCIdentityRoot((*I->begin())->getOperand(0));

      return Nested;
   }

   /// Uninitialize the current state.
   void clear() {
      KnownSafe = false;
   }

   /// Is this ref count initialized and tracking a ref count ptr.
   bool isTrackingRefCount() const { return Transition.isValid(); }

   /// Are we tracking an instruction currently? This returns false when given an
   /// uninitialized ReferenceCountState.
   bool isTrackingRefCountInst() const {
      return Transition.isValid() && Transition.isMutator();
   }

   /// Are we tracking a source of ref counts? This currently means that we are
   /// tracking an argument that is @owned. In the future this will include
   /// return values of functions that are @owned.
   bool isTrackingRefCountSource() const {
      return Transition.isValid() && Transition.isEndPoint();
   }

   /// Return the increment we are tracking.
   RCStateTransition::mutator_range getInstructions() const {
      return Transition.getMutators();
   }

   /// Returns true if I is in the instructions we are tracking.
   bool containsInstruction(PILInstruction *I) const {
      return Transition.isValid() && Transition.containsMutator(I);
   }

   /// Return the value with reference semantics that is the operand of our
   /// increment.
   PILValue getRCRoot() const {
      assert(RCRoot && "Value should never be null here");
      return RCRoot;
   }

   /// Returns true if we have a valid value that we are tracking.
   bool hasRCRoot() const {
      return (bool)RCRoot;
   }

   /// This retain is known safe if the operand we are tracking was already known
   /// incremented previously. This occurs when you have nested increments.
   bool isKnownSafe() const { return KnownSafe; }

   /// Set KnownSafe to true if \p NewValue is true. If \p NewValue is false,
   /// this is a no-op.
   void updateKnownSafe(bool NewValue) {
      KnownSafe |= NewValue;
   }
};

//===----------------------------------------------------------------------===//
//                         Bottom Up Ref Count State
//===----------------------------------------------------------------------===//

class BottomUpRefCountState : public RefCountState {
public:
   /// Sequence of states that a value with reference semantics can go through
   /// when visiting decrements bottom up. The reason why I have this separate
   /// from TopDownSubstruct is I think it gives more clarity to the algorithm by
   /// giving it typed form.
   enum class LatticeState {
      None,               ///< The pointer has no information associated with it.
      Decremented,        ///< The pointer will be decremented.
      MightBeUsed,        ///< The pointer will be used and then at this point
      ///  be decremented
         MightBeDecremented, ///< The pointer might be decremented again implying
      ///  that we cannot, without being known safe remove
      ///  this decrement.
   };

private:
   using SuperTy = RefCountState;

   /// Current place in the sequence of the value.
   LatticeState LatState = LatticeState::None;

   /// True if we have seen a NonARCUser of this instruction. This means bottom
   /// up assuming we have this property as a meet over all paths property, we
   /// know that all releases we see are known safe.
   bool FoundNonARCUser = false;

public:
   BottomUpRefCountState() = default;
   ~BottomUpRefCountState() = default;
   BottomUpRefCountState(const BottomUpRefCountState &) = default;
   BottomUpRefCountState &operator=(const BottomUpRefCountState &) = default;
   BottomUpRefCountState(BottomUpRefCountState &&) = default;
   BottomUpRefCountState &operator=(BottomUpRefCountState &&) = default;

   /// Return true if the release can be moved to the retain.
   bool isCodeMotionSafe() const {
      return LatState != LatticeState::MightBeDecremented;
   }

   /// Initializes/reinitialized the state for I. If we reinitialize we return
   /// true.
   bool initWithMutatorInst(ImmutablePointerSet<PILInstruction> *I,
                            RCIdentityFunctionInfo *RCFI);

   /// Update this reference count's state given the instruction \p I. \p
   /// InsertPt is the point furthest up the CFG where we can move the currently
   /// tracked reference count.
   void
   updateForSameLoopInst(PILInstruction *I,
                         ImmutablePointerSetFactory<PILInstruction> &SetFactory,
                         AliasAnalysis *AA);

   /// Update this reference count's state given the instruction \p I. \p
   /// InsertPts are the points furthest up the CFG where we can move the
   /// currently tracked reference count.
   //
   /// The main difference in between this routine and update for same loop inst
   /// is that if we see any decrements on a value, we treat it as being
   /// guaranteed used. We treat any uses as regular uses.
   void updateForDifferentLoopInst(
      PILInstruction *I,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory,
      AliasAnalysis *AA);

   // Determine the conservative effect of the given list of predecessor
   // terminators upon this reference count.
   void updateForPredTerminators(
      ArrayRef<PILInstruction *> PredTerms,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory,
      AliasAnalysis *AA);

   /// Attempt to merge \p Other into this ref count state. Return true if we
   /// succeed and false otherwise.
   bool merge(const BottomUpRefCountState &Other);

   /// Returns true if the passed in ref count inst matches the ref count inst
   /// we are tracking. This handles generically retains/release.
   bool isRefCountInstMatchedToTrackedInstruction(PILInstruction *RefCountInst);

   /// Uninitialize the current state.
   void clear();

private:
   /// Return true if we *might* remove this instruction.
   ///
   /// This is a conservative query given the information we know, so as we
   /// perform the dataflow it may change value.
   bool mightRemoveMutators();

   /// Can we guarantee that the given reference counted value has been modified?
   bool isRefCountStateModified() const;

   /// Returns true if given the current lattice state, do we care if the value
   /// we are tracking is decremented.
   bool valueCanBeDecrementedGivenLatticeState() const;

   /// If advance the state's sequence appropriately for a decrement. If we do
   /// advance return true. Otherwise return false.
   bool handleDecrement();

   /// Check if PotentialDecrement can decrement the reference count associated
   /// with the value we are tracking. If so advance the state's sequence
   /// appropriately and return true. Otherwise return false.
   bool handlePotentialDecrement(PILInstruction *Decrement, AliasAnalysis *AA);

   /// Returns true if given the current lattice state, do we care if the value
   /// we are tracking is used.
   bool valueCanBeUsedGivenLatticeState() const;

   /// Given the current lattice state, if we have seen a use, advance the
   /// lattice state. Return true if we do so and false otherwise. \p InsertPt is
   /// the location where if \p PotentialUser is a user of this ref count, we
   /// would insert a release.
   bool handleUser(PILValue RCIdentity,
                   ImmutablePointerSetFactory<PILInstruction> &SetFactory,
                   AliasAnalysis *AA);

   /// Check if PotentialUser could be a use of the reference counted value that
   /// requires user to be alive. If so advance the state's sequence
   /// appropriately and return true. Otherwise return false.
   bool
   handlePotentialUser(PILInstruction *PotentialUser,
                       ImmutablePointerSetFactory<PILInstruction> &SetFactory,
                       AliasAnalysis *AA);

   /// Returns true if given the current lattice state, do we care if the value
   /// we are tracking is used.
   bool valueCanBeGuaranteedUsedGivenLatticeState() const;

   /// Given the current lattice state, if we have seen a use, advance the
   /// lattice state. Return true if we do so and false otherwise. \p InsertPt is
   /// the location where if \p PotentialUser is a user of this ref count, we
   /// would insert a release.
   bool
   handleGuaranteedUser(PILValue RCIdentity,
                        ImmutablePointerSetFactory<PILInstruction> &SetFactory,
                        AliasAnalysis *AA);

   /// Check if PotentialGuaranteedUser can use the reference count associated
   /// with the value we are tracking. If so advance the state's sequence
   /// appropriately and return true. Otherwise return false.
   bool handlePotentialGuaranteedUser(
      PILInstruction *User,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory,
      AliasAnalysis *AA);

   /// We have a matching ref count inst. Return true if we advance the sequence
   /// and false otherwise.
   bool handleRefCountInstMatch(PILInstruction *RefCountInst);
};

//===----------------------------------------------------------------------===//
//                          Top Down Ref Count State
//===----------------------------------------------------------------------===//

class TopDownRefCountState : public RefCountState {
public:
   /// Sequence of states that a value with reference semantics can go through
   /// when visiting decrements bottom up. The reason why I have this separate
   /// from BottomUpRefCountState is I think it gives more clarity to the
   /// algorithm by giving it typed form.
   enum class LatticeState {
      None,               ///< The pointer has no information associated with it.
      Incremented,        ///< The pointer has been incremented.
      MightBeDecremented, ///< The pointer has been incremented and might be
      ///  decremented. be decremented again implying
         MightBeUsed,        ///< The pointer has been incremented,
   };

private:
   using SuperTy = RefCountState;

   /// Current place in the sequence of the value.
   LatticeState LatState = LatticeState::None;

public:
   TopDownRefCountState() = default;
   ~TopDownRefCountState() = default;
   TopDownRefCountState(const TopDownRefCountState &) = default;
   TopDownRefCountState &operator=(const TopDownRefCountState &) = default;
   TopDownRefCountState(TopDownRefCountState &&) = default;
   TopDownRefCountState &operator=(TopDownRefCountState &&) = default;

   /// Return true if the retain can be moved to the release.
   bool isCodeMotionSafe() const {
      return LatState != LatticeState::MightBeUsed;
   }

   /// Initializes/reinitialized the state for I. If we reinitialize we return
   /// true.
   bool initWithMutatorInst(ImmutablePointerSet<PILInstruction> *I,
                            RCIdentityFunctionInfo *RCFI);

   /// Initialize the state given the consumed argument Arg.
   void initWithArg(PILFunctionArgument *Arg);

   /// Initialize this RefCountState with an instruction which introduces a new
   /// ref count at +1.
   void initWithEntranceInst(ImmutablePointerSet<PILInstruction> *I,
                             PILValue RCIdentity);

   /// Uninitialize the current state.
   void clear();

   /// Update this reference count's state given the instruction \p I. \p
   /// InsertPt is the point furthest up the CFG where we can move the currently
   /// tracked reference count.
   void
   updateForSameLoopInst(PILInstruction *I,
                         ImmutablePointerSetFactory<PILInstruction> &SetFactory,
                         AliasAnalysis *AA);

   /// Update this reference count's state given the instruction \p I. \p
   /// InsertPts are the points furthest up the CFG where we can move the
   /// currently tracked reference count.
   ///
   /// The main difference in between this routine and update for same loop inst
   /// is that if we see any decrements on a value, we treat it as being
   /// guaranteed used. We treat any uses as regular uses.
   void updateForDifferentLoopInst(
      PILInstruction *I,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory,
      AliasAnalysis *AA);

   /// Returns true if the passed in ref count inst matches the ref count inst
   /// we are tracking. This handles generically retains/release.
   bool isRefCountInstMatchedToTrackedInstruction(PILInstruction *RefCountInst);

   /// Attempt to merge \p Other into this ref count state. Return true if we
   /// succeed and false otherwise.
   bool merge(const TopDownRefCountState &Other);

private:
   /// Can we guarantee that the given reference counted value has been modified?
   bool isRefCountStateModified() const;

   /// Returns true if given the current lattice state, do we care if the value
   /// we are tracking is decremented.
   bool valueCanBeDecrementedGivenLatticeState() const;

   /// If advance the state's sequence appropriately for a decrement. If we do
   /// advance return true. Otherwise return false.
   bool handleDecrement(PILInstruction *PotentialDecrement,
                        ImmutablePointerSetFactory<PILInstruction> &SetFactory);

   /// Check if PotentialDecrement can decrement the reference count associated
   /// with the value we are tracking. If so advance the state's sequence
   /// appropriately and return true. Otherwise return false.
   bool handlePotentialDecrement(
      PILInstruction *PotentialDecrement,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory,
      AliasAnalysis *AA);

   /// Returns true if given the current lattice state, do we care if the value
   /// we are tracking is used.
   bool valueCanBeUsedGivenLatticeState() const;

   /// Given the current lattice state, if we have seen a use, advance the
   /// lattice state. Return true if we do so and false otherwise.
   bool handleUser(PILInstruction *PotentialUser,
                   PILValue RCIdentity, AliasAnalysis *AA);

   /// Check if PotentialUser could be a use of the reference counted value that
   /// requires user to be alive. If so advance the state's sequence
   /// appropriately and return true. Otherwise return false.
   bool handlePotentialUser(PILInstruction *PotentialUser, AliasAnalysis *AA);

   /// Returns true if given the current lattice state, do we care if the value
   /// we are tracking is used.
   bool valueCanBeGuaranteedUsedGivenLatticeState() const;

   /// Given the current lattice state, if we have seen a use, advance the
   /// lattice state. Return true if we do so and false otherwise.
   bool
   handleGuaranteedUser(PILInstruction *PotentialGuaranteedUser,
                        PILValue RCIdentity,
                        ImmutablePointerSetFactory<PILInstruction> &SetFactory,
                        AliasAnalysis *AA);

   /// Check if PotentialGuaranteedUser can use the reference count associated
   /// with the value we are tracking. If so advance the state's sequence
   /// appropriately and return true. Otherwise return false.
   bool handlePotentialGuaranteedUser(
      PILInstruction *PotentialGuaranteedUser,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory,
      AliasAnalysis *AA);

   /// We have a matching ref count inst. Return true if we advance the sequence
   /// and false otherwise.
   bool handleRefCountInstMatch(PILInstruction *RefCountInst);
};

// These static asserts are here for performance reasons.
static_assert(std::is_trivially_copyable<BottomUpRefCountState>::value,
              "All ref count states must be trivially copyable");
static_assert(std::is_trivially_copyable<TopDownRefCountState>::value,
              "All ref count states must be trivially copyable");

} // end polar namespace

namespace llvm {

raw_ostream &operator<<(raw_ostream &OS,
                        polar::BottomUpRefCountState::LatticeState S);
raw_ostream &operator<<(raw_ostream &OS,
                        polar::TopDownRefCountState::LatticeState S);

} // end namespace llvm

#endif // POLARPHP_PIL_OPTIMIZER_INTERNAL_ARC_REFCOUNTSTATE_H
